package org.example;

import java.util.Arrays;

/**
 * 使用堆模拟实现优先级队列
 */
public class TestHeap {

    private int[] elem;
    private int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 创建大根堆
     * @param arr
     */
    public void createHeap1(int[] arr) {
        for (int parent= (arr.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown1(arr, parent, arr.length);
        }
    }

    /**
     * 向下调整(大根堆)
     * @param arr
     * @param parent
     * @param size
     */
    private void shiftDown1(int[] arr, int parent, int size) {
        int child = 2 * parent + 1;
        while (child < size && child + 1 < arr.length) {
            if (arr[child + 1] > arr[child]) {
                child = child + 1;
            }
            if (arr[child] > arr[parent]) {
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 创建小根堆
     * @param arr
     */
    public void createHeap2(int[] arr) {
        for (int parent= (arr.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown2(arr, parent, arr.length);
        }
    }
    /**
     * 向下调整(小根堆)
     * @param arr
     * @param parent
     * @param length
     */
    private void shiftDown2(int[] arr, int parent, int length) {
        int child = 2 * parent + 1;
        while (child < length && child + 1 < arr.length) {
            if (arr[child + 1] < arr[child]) {
                child = child + 1;
            }
            if (arr[child] < arr[parent]) {
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 入队列
     * 入队列仍然要保持大根堆的性质
     */
    public void push(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[usedSize] = val;
        usedSize++;
        shiftUp(elem, usedSize - 1);
    }

    /**
     * 向上调整
     * @param elem
     * @param child
     */
    private void shiftUp(int[] elem, int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 出队列
     * 出队列仍然要保持大根堆的性质
     * 每次删除的都是优先级最高的元素，因此只需要将最后一个元素放到堆顶，然后将堆的大小减一，再进行一次向下调整即可
     */
    public void pollHeap() {
        if (isEmpty()) {
            System.out.println("优先级队列为空");
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize - 1] = tmp;
        usedSize--;
        shiftDown1(elem, 0, usedSize);
    }

    private boolean isEmpty() {
        return usedSize == 0;
    }
}
